package com.zhangx.datastructure.lineartable;

import java.util.Random;
import java.util.RandomAccess;

public class ZxLinkList {

    private Node nodes = new Node();
    private int size = 0;

    public ZxLinkList(){
//        Node first = new Node();
//        first.data = -1;
//
//        Node n1 = new Node();
//        n1.data = 0;
//
//        Node n2 = new Node();
//        n2.data = 1;
//
//        Node n3 = new Node();
//        n3.data = 2;
//
//
//        first.next = n1;
//        n1.next = n2;
//        n2.next = n3;
//        nodes.next = first;


    }

    /**
     *  头插法创建链表
     */
    public void createListHead(){
        Random random = new Random();
        int count = 0;

        Node head = new Node();
        head.data = -99;
//        head.next = null;

        Node node;
//        头插法
        for (int i = 0; i < 10; i++) {
            count++;
            node = new Node();
            node.data = i;
//            这一行重要，将node插入到头结点和头结点的next之间
//            P67页图示很明白
            node.next = head.next;
            head.next = node;
        }
        size = count;
        nodes = head;

    }

    /**
     *  尾插法
     */
    public void createListTail(){
        int count = 0;
//        队尾 其实就是nodes
        Node r = null;
//        要插入的元素
        Node p = null;
//        初始化链表
        nodes = new Node();
        r = nodes;
        for (int i = 1; i < 10; i++) {
            count++;
            p = new Node();
            p.data = i;
            r.next = p;
            r = p;
        }
        r.next = null;
        size = count;
    }

    public Node getElem(int index){
        Node t = nodes;
        int i = 0;
        while (t.next!=null){
            if (i == index){
                return t;
            }
            i++;
            t = t.next;
        }
        return null;

    }

    /**
     * 考虑队列头和尾
     * @param item
     * @param index
     */
    public void insert(Node item,int index){
        Node t = nodes;
        int i = 0;
//        头
        if (index == -1){
            item.next = nodes;
            nodes = item;
            return;
        }
        while (t.next!=null){
            if (i == index){
                item.next = t.next;
                t.next = item;
                return;
            }
            i++;
            t = t.next;
        }
//        尾
        t.next = item;
    }

    public int delete(int index){
        Node t = nodes;
        int i = 0;
        int data = 0;
//        头
        if (index == -1){
            data = nodes.data;
            nodes = nodes.next;
            return data;
        }
        while (t.next!=null){
            if (i == index){
                data = t.data;
                t.next = t.next.next;
                return data;
            }
            i++;
            t = t.next;
        }
        return -100;
    }

    @Override
    public String toString() {
        String s = "";
        Node t = nodes;
        int i = 0;
        while (t!=null){
            s = s + t.data + ",";
            t = t.next;
        }
        return s;
    }

    public static void main(String[] args) {
        ZxLinkList linkList = new ZxLinkList();
//        System.out.println(linkList.getElem(3).data);
//        System.out.println(linkList);
//        ZxLinkList.Node add = new ZxLinkList.Node();
//        add.data = 99;
//        linkList.insert(add,10);
//        System.out.println(linkList);
//        System.out.println(linkList.delete(3));;
//        System.out.println(linkList);

//        System.out.println("头插法");
//        linkList.createListHead();
//        System.out.println(linkList);
        System.out.println("尾插法");
        linkList.createListTail();
        System.out.println(linkList);
    }


    public static class Node{
        private int data;
        private Node next;
    }
}
